<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="en">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.3" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon.png?v=5.1.3">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32.png?v=5.1.3">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16.png?v=5.1.3">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.3" color="#222">





  <meta name="keywords" content="scheme,continuation-passing style" />










<meta name="description" content="之前在How to implement a programming language in JavaScript这篇教程中看到了CPS transformer的js实现，决定复习一下CPS变换，于是写了一个CPS transformer。本文的实现使用了R. Kent Dybvig编写的Chez Scheme的pattern matching库，具体使用方法可以查看这个链接。">
<meta name="keywords" content="scheme,continuation-passing style">
<meta property="og:type" content="article">
<meta property="og:title" content="CPS Transformer的实现">
<meta property="og:url" content="https://arucil.github.io/2018/cps-transformer-implementation/index.html">
<meta property="og:site_name" content="Plodsoft&#39;s Blog">
<meta property="og:description" content="之前在How to implement a programming language in JavaScript这篇教程中看到了CPS transformer的js实现，决定复习一下CPS变换，于是写了一个CPS transformer。本文的实现使用了R. Kent Dybvig编写的Chez Scheme的pattern matching库，具体使用方法可以查看这个链接。">
<meta property="og:locale" content="en">
<meta property="og:updated_time" content="2018-04-04T04:50:58.008Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="CPS Transformer的实现">
<meta name="twitter:description" content="之前在How to implement a programming language in JavaScript这篇教程中看到了CPS transformer的js实现，决定复习一下CPS变换，于是写了一个CPS transformer。本文的实现使用了R. Kent Dybvig编写的Chez Scheme的pattern matching库，具体使用方法可以查看这个链接。">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.3',
    sidebar: {"position":"left","display":"always","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: 'Author'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="https://arucil.github.io/2018/cps-transformer-implementation/"/>





  <title>CPS Transformer的实现 | Plodsoft's Blog</title>
  








</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="en">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">Plodsoft's Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <h1 class="site-subtitle" itemprop="description">Programming Language Enthusiast</h1>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
            Home
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags" rel="section">
            
            Tags
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
            Archives
          </a>
        </li>
      
        
        <li class="menu-item menu-item-games">
          <a href="/games" rel="section">
            
            Games
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://arucil.github.io/2018/cps-transformer-implementation/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="Plodsoft">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="https://avatars0.githubusercontent.com/u/5410312?v=4&s=460">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Plodsoft's Blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">CPS Transformer的实现</h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2018-04-03T00:00:00+08:00">
                2018-04-03
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/2018/cps-transformer-implementation/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count disqus-comment-count"
                        data-disqus-identifier="2018/cps-transformer-implementation/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>之前在<a href="http://lisperator.net/pltut/" target="_blank" rel="external">How to implement a programming language in JavaScript</a>这篇教程中看到了CPS transformer的js实现，决定复习一下CPS变换，于是写了一个CPS transformer。<br>本文的实现使用了R. Kent Dybvig编写的<a href="https://www.cs.indiana.edu/chezscheme/match/" target="_blank" rel="external">Chez Scheme的pattern matching库</a>，具体使用方法可以查看<a href="https://www.cs.indiana.edu/chezscheme/match/" target="_blank" rel="external">这个链接</a>。  </p>
<a id="more"></a>
<p>主要函数<code>(cps exp k)</code>包含两个参数：exp是要进行CPS变换的表达式，k是用来接收CPS变换后的表达式的continuation。对于数字、字符串、变量这样的简单表达式，直接把原表达式传给k：<br><figure class="highlight scheme"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div></pre></td><td class="code"><pre><div class="line">(<span class="name"><span class="builtin-name">define</span></span> (<span class="name">cps</span> exp k)</div><div class="line">  (<span class="name">match</span> exp</div><div class="line">   [,v</div><div class="line">    (<span class="name">guard</span></div><div class="line">     (<span class="name"><span class="builtin-name">or</span></span> (<span class="name"><span class="builtin-name">number?</span></span> v)</div><div class="line">         (<span class="name"><span class="builtin-name">symbol?</span></span> v)</div><div class="line">         (<span class="name"><span class="builtin-name">boolean?</span></span> v)</div><div class="line">         (<span class="name"><span class="builtin-name">string?</span></span> v)))</div><div class="line">    (<span class="name">k</span> v)]</div></pre></td></tr></table></figure></p>
<p>接下来是<code>if</code>表达式的处理。首先要把条件表达式进行CPS变换，然后用变换后的条件表达式重新组装成if表达式：<br><figure class="highlight scheme"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div></pre></td><td class="code"><pre><div class="line">[(<span class="name"><span class="builtin-name">if</span></span> ,test ,conseq ,alt)</div><div class="line"> (<span class="name">cps</span> test</div><div class="line">      (<span class="name"><span class="builtin-name">lambda</span></span> (v)</div><div class="line">        `(if ,v</div><div class="line">             ,(cps conseq k)</div><div class="line">             ,(cps alt k))))]</div></pre></td></tr></table></figure></p>
<p>这里的conseq和alt两个if分支都用到了k，但没有处理重复的continuation的问题，因此会造成以下的代码膨胀问题：<br><figure class="highlight scheme"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div></pre></td><td class="code"><pre><div class="line">(<span class="name"><span class="builtin-name">begin</span></span> (<span class="name"><span class="builtin-name">if</span></span> <span class="literal">#t</span> <span class="number">123</span> <span class="number">456</span>) ... 大量计算 ...)</div><div class="line"><span class="comment">;; =&gt; CPS-ed to</span></div><div class="line">(<span class="name"><span class="builtin-name">if</span></span> <span class="literal">#t</span></div><div class="line">    (<span class="name"><span class="builtin-name">begin</span></span> <span class="number">123</span> ... 大量计算 ...)</div><div class="line">    (<span class="name"><span class="builtin-name">begin</span></span> <span class="number">456</span> ... 大量计算 ...))</div></pre></td></tr></table></figure></p>
<p>上面的大量计算部分的代码在CPS变换后的表达式中重复出现了两次。解决的方法也很简单，把continuation用<code>let</code>保存起来就行了。王垠的40行代码对这个地方做了一点优化，感兴趣的同学可以看一下。  </p>
<p><code>set!</code>表达式的处理和<code>if</code>大同小异：<br><figure class="highlight scheme"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div></pre></td><td class="code"><pre><div class="line">[(<span class="name"><span class="builtin-name">set!</span></span> ,var ,exp1)</div><div class="line"> (<span class="name">cps</span> exp1</div><div class="line">      (<span class="name"><span class="builtin-name">lambda</span></span> (v)</div><div class="line">        (<span class="name">k</span> `(set! ,var ,v))))]</div></pre></td></tr></table></figure></p>
<p>接下来是内置函数调用的变换。由于内置函数不使用CPS方式进行调用，因此要进行特殊处理。<br><figure class="highlight scheme"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div></pre></td><td class="code"><pre><div class="line">[(,rator ,rands ...)</div><div class="line"> (<span class="name">guard</span> (<span class="name"><span class="builtin-name">memq</span></span> rator '(cons car cdr null? + - * / &gt; &lt; = &gt;= &lt;= not)))</div><div class="line"> (<span class="name">cps*</span> rands</div><div class="line">       (<span class="name"><span class="builtin-name">lambda</span></span> (args)</div><div class="line">         (<span class="name">k</span> `(,rator ,@args))))]</div></pre></td></tr></table></figure></p>
<p>上面的<code>cps*</code>函数对参数列表中每个参数表达式进行CPS变换，把变换的结果收集到一个list中。<code>cps*</code>函数的定义如下：<br><figure class="highlight scheme"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div></pre></td><td class="code"><pre><div class="line">(<span class="name"><span class="builtin-name">define</span></span> (<span class="name">cps*</span> exp* k)</div><div class="line">  (<span class="name"><span class="builtin-name">cond</span></span></div><div class="line">   [(<span class="name"><span class="builtin-name">null?</span></span> exp*)</div><div class="line">    (<span class="name">k</span> '())]</div><div class="line">   [<span class="name"><span class="builtin-name">else</span></span></div><div class="line">    (<span class="name">cps</span> (<span class="name"><span class="builtin-name">car</span></span> exp*)</div><div class="line">         (<span class="name"><span class="builtin-name">lambda</span></span> (v1)</div><div class="line">           (<span class="name">cps*</span> (<span class="name"><span class="builtin-name">cdr</span></span> exp*)</div><div class="line">                 (<span class="name"><span class="builtin-name">lambda</span></span> (v*)</div><div class="line">                   (<span class="name">k</span> (<span class="name"><span class="builtin-name">cons</span></span> v1 v*))))))]))</div></pre></td></tr></table></figure></p>
<p>展开<code>begin</code>表达式：<br><figure class="highlight scheme"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div></pre></td><td class="code"><pre><div class="line">[(<span class="name"><span class="builtin-name">begin</span></span> ,exp1 ,exps ...)</div><div class="line"> (<span class="name">cps-body</span> (<span class="name"><span class="builtin-name">cons</span></span> exp1 exps) k)]</div></pre></td></tr></table></figure></p>
<p><code>cps-body</code>函数用于对表达式序列进行CPS变换，并丢弃除了最后一个表达式之外的返回值。<code>cps-body</code>的定义如下：<br><figure class="highlight"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div></pre></td><td class="code"><pre><div class="line">(<span class="name"><span class="builtin-name">define</span></span> (<span class="name">cps-body</span> exp* k)</div><div class="line">  (<span class="name"><span class="builtin-name">cond</span></span></div><div class="line">   [(<span class="name"><span class="builtin-name">null?</span></span> (<span class="name"><span class="builtin-name">cdr</span></span> exp*))</div><div class="line">    (<span class="name">cps</span> (<span class="name"><span class="builtin-name">car</span></span> exp*) k)]</div><div class="line">   [<span class="name"><span class="builtin-name">else</span></span></div><div class="line">    (<span class="name">cps</span> (<span class="name"><span class="builtin-name">car</span></span> exp*)</div><div class="line">         (<span class="name"><span class="builtin-name">lambda</span></span> (v1)</div><div class="line">           `(begin</div><div class="line">             ,v1</div><div class="line">             ,(cps-body (cdr exp*)</div><div class="line">                        k))))]))])</div></pre></td></tr></table></figure></p>
<p>例如<code>(begin (set! a (foo 7)) (set! b (bar 3 4)))</code>经过变换后变成：<br><figure class="highlight scheme"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div></pre></td><td class="code"><pre><div class="line">(<span class="name">foo</span> (<span class="name"><span class="builtin-name">lambda</span></span> (v.1)</div><div class="line">       (<span class="name"><span class="builtin-name">begin</span></span></div><div class="line">        (<span class="name"><span class="builtin-name">set!</span></span> a v.1)</div><div class="line">        (<span class="name">bar</span> (<span class="name"><span class="builtin-name">lambda</span></span> (v.2)</div><div class="line">               (<span class="name"><span class="builtin-name">set!</span></span> b v.2))</div><div class="line">             <span class="number">3</span> <span class="number">4</span>)))</div><div class="line">     <span class="number">7</span>)</div></pre></td></tr></table></figure></p>
<p>值得一提的是在《Lisp in Small Pieces》书中P177有一个CPS Transformer的实现，其中有对<code>begin</code>进行CPS变换的部分：<br><figure class="highlight scheme"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div></pre></td><td class="code"><pre><div class="line">(<span class="name"><span class="builtin-name">define</span></span> (<span class="name">cps-begin</span> e)</div><div class="line">  (<span class="name"><span class="builtin-name">if</span></span> (<span class="name"><span class="builtin-name">pair?</span></span> e)</div><div class="line">      (<span class="name"><span class="builtin-name">if</span></span> (<span class="name"><span class="builtin-name">pair?</span></span> (<span class="name"><span class="builtin-name">cdr</span></span> e))</div><div class="line">          (<span class="name"><span class="builtin-name">let</span></span> ((<span class="name">void</span> (<span class="name">gensym</span> <span class="string">"void"</span>)))</div><div class="line">            (<span class="name"><span class="builtin-name">lambda</span></span> (k)</div><div class="line">              ((<span class="name">cps</span> (<span class="name"><span class="builtin-name">car</span></span> e))</div><div class="line">               (<span class="name"><span class="builtin-name">lambda</span></span> (a)</div><div class="line">                 ((<span class="name">cps-begin</span> (<span class="name"><span class="builtin-name">cdr</span></span> e))</div><div class="line">                  (<span class="name"><span class="builtin-name">lambda</span></span> (b)</div><div class="line">                    (<span class="name">k</span> `((lambda (,void) ,b) ,a))))))))</div><div class="line">          (<span class="name">cps</span> (<span class="name"><span class="builtin-name">car</span></span> e)))</div><div class="line">      (<span class="name">cps</span> '())))</div></pre></td></tr></table></figure></p>
<p>是错误的，书中的代码会把前面的<code>begin</code>表达式变换成：<br><figure class="highlight scheme"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div></pre></td><td class="code"><pre><div class="line">(<span class="name">foo</span> (<span class="name"><span class="builtin-name">lambda</span></span> (v.1)</div><div class="line">       (<span class="name">bar</span> (<span class="name"><span class="builtin-name">lambda</span></span> (v.2)</div><div class="line">              ((<span class="name"><span class="builtin-name">lambda</span></span> (void)</div><div class="line">                 (<span class="name"><span class="builtin-name">set!</span></span> b v.2))</div><div class="line">               (<span class="name"><span class="builtin-name">set!</span></span> a v.1)))</div><div class="line">            <span class="number">3</span> <span class="number">4</span>))</div><div class="line">     <span class="number">7</span>)</div></pre></td></tr></table></figure></p>
<p>对<code>bar</code>的调用发生在对<code>a</code>的赋值之前，显然不正确。  </p>
<p>对<code>lambda</code>表达式进行变换时，要在参数列表中加上一个额外的continuation参数。<br><figure class="highlight scheme"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div></pre></td><td class="code"><pre><div class="line">[(<span class="name"><span class="builtin-name">lambda</span></span> (,params ...) ,body1 ,body* ...)</div><div class="line"> (<span class="name"><span class="builtin-name">let</span></span> ([<span class="name">k1</span> (<span class="name">gen-sym</span> <span class="symbol">'k</span>)])</div><div class="line">   (<span class="name">k</span> `(lambda (,k1 ,@params)</div><div class="line">         ,(cps-body (cons body1 body*)</div><div class="line">                    (lambda (v)</div><div class="line">                      `(,k1 ,v))))))]</div></pre></td></tr></table></figure></p>
<p>这里使用了自定义的<code>gen-sym</code>函数生成不重复的symbol，避免参数重名。把额外的continuation参数放到第一个参数的位置是为了可以方便地支持不定参数的函数。<br>要注意的是，这里传给<code>cps-body</code>k参数的是<code>(lambda (v) `(,k1 ,v))</code>，这样函数才能正确地把返回值传给<code>k1</code>continuation。例如<code>(lambda (x) x)</code>会变换成<code>(lambda (k.1 x) (k.1 x))</code>。  </p>
<p>最后是函数调用的变换：<br><figure class="highlight scheme"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div></pre></td><td class="code"><pre><div class="line">[(,rator ,rands ...)</div><div class="line"> (<span class="name">cps*</span> (<span class="name"><span class="builtin-name">cons</span></span> rator rands)</div><div class="line">       (<span class="name"><span class="builtin-name">lambda</span></span> (args)</div><div class="line">         (<span class="name"><span class="builtin-name">let</span></span> ([<span class="name">k1</span> (<span class="name">gen-sym</span> <span class="symbol">'v</span>)])</div><div class="line">           `(,(car args)</div><div class="line">             (lambda (,k1)</div><div class="line">               ,(k k1))</div><div class="line">               ,@(cdr args)))))]</div></pre></td></tr></table></figure></p>
<p>在函数调用中增加了一个continuation参数，把函数返回的结果（<code>v1</code>表示的变量）传给原先的k。  </p>
<p><code>cps</code>函数完成了，要调用<code>cps</code>函数的话，要定义一个<code>id</code>函数，把CPS变换的结果原样返回：<br><figure class="highlight scheme"><table><tr><td class="gutter"><pre><div class="line">1</div></pre></td><td class="code"><pre><div class="line">(<span class="name"><span class="builtin-name">define</span></span> (<span class="name">id</span> x) x)</div></pre></td></tr></table></figure></p>
<p>测试结果：<br><figure class="highlight scheme"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div></pre></td><td class="code"><pre><div class="line">&gt; (cps '(begin</div><div class="line">          (<span class="name"><span class="builtin-name">set!</span></span> a (<span class="name">foo</span> <span class="number">7</span>))</div><div class="line">          (set! b (cons 1 (bar 3 4))))</div><div class="line">       id)</div><div class="line">(<span class="name">foo</span> (<span class="name"><span class="builtin-name">lambda</span></span> (v.1)</div><div class="line">       (<span class="name"><span class="builtin-name">begin</span></span></div><div class="line">        (<span class="name"><span class="builtin-name">set!</span></span> a v.1)</div><div class="line">        (<span class="name">bar</span> (<span class="name"><span class="builtin-name">lambda</span></span> (v.2)</div><div class="line">               (<span class="name"><span class="builtin-name">set!</span></span> b (<span class="name"><span class="builtin-name">cons</span></span> <span class="number">1</span> v.2)))</div><div class="line">             <span class="number">3</span> <span class="number">4</span>)))</div><div class="line">     <span class="number">7</span>)</div><div class="line">     </div><div class="line">&gt; (cps '((lambda (n)</div><div class="line">           (<span class="name"><span class="builtin-name">if</span></span> (<span class="name"><span class="builtin-name">&lt;</span></span> n <span class="number">2</span>)</div><div class="line">               n</div><div class="line">               (<span class="name"><span class="builtin-name">+</span></span> (<span class="name">fib</span> (<span class="name"><span class="builtin-name">-</span></span> n <span class="number">1</span>))</div><div class="line">                  (fib (- n 2)))))</div><div class="line">         10)</div><div class="line">       id)</div><div class="line">((<span class="name"><span class="builtin-name">lambda</span></span> (k.1 n)</div><div class="line">   (<span class="name"><span class="builtin-name">if</span></span> (<span class="name"><span class="builtin-name">&lt;</span></span> n <span class="number">2</span>)</div><div class="line">       (<span class="name">k.1</span> n)</div><div class="line">       (<span class="name">fib</span> (<span class="name"><span class="builtin-name">lambda</span></span> (v.1)</div><div class="line">              (<span class="name">fib</span> (<span class="name"><span class="builtin-name">lambda</span></span> (v.2)</div><div class="line">                     (<span class="name">k.1</span> (<span class="name"><span class="builtin-name">+</span></span> v.1 v.2)))</div><div class="line">                   (<span class="name"><span class="builtin-name">-</span></span> n <span class="number">2</span>)))</div><div class="line">            (<span class="name"><span class="builtin-name">-</span></span> n <span class="number">1</span>))))</div><div class="line"> (<span class="name"><span class="builtin-name">lambda</span></span> (v.3) v.3)</div><div class="line"> <span class="number">10</span>)</div></pre></td></tr></table></figure></p>
<p>完整的源码在<a href="https://gist.github.com/arucil/3f308b943487da793d9e9a4f24e659c5" target="_blank" rel="external">cps.scm</a>。</p>

      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/Scheme/" rel="tag"># Scheme</a>
          
            <a href="/tags/Continuation-Passing-Style/" rel="tag"># Continuation-Passing Style</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2017/dynamic-wind-implementation/" rel="next" title="dynamic-wind的实现">
                <i class="fa fa-chevron-left"></i> dynamic-wind的实现
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2018/memoization-in-haskell/" rel="prev" title="Memoization in Haskell">
                Memoization in Haskell <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          
  
    <div class="comments" id="comments">
      <div id="disqus_thread">
        <noscript>
          Please enable JavaScript to view the
          <a href="https://disqus.com/?ref_noscript">comments powered by Disqus.</a>
        </noscript>
      </div>
    </div>
  


        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      

      <section class="site-overview-wrap sidebar-panel sidebar-panel-active">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image"
                src="https://avatars0.githubusercontent.com/u/5410312?v=4&s=460"
                alt="Plodsoft" />
            
              <p class="site-author-name" itemprop="name">Plodsoft</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">4</span>
                  <span class="site-state-item-name">posts</span>
                </a>
              </div>
            

            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">7</span>
                  <span class="site-state-item-name">tags</span>
                </a>
              </div>
            

          </nav>

          

          <div class="links-of-author motion-element">
            
          </div>

          
          

          
          

          

        </div>
      </section>

      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2018</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Plodsoft</span>

  
</div>


  <div class="powered-by">Powered by <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a></div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">Theme &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Gemini</a> v5.1.3</div>




        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>

  
  <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>

  
  <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>

  
  <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.3"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.3"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.3"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.3"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.3"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.3"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.3"></script>



  


  

    
      <script id="dsq-count-scr" src="https://plodsoft.disqus.com/count.js" async></script>
    

    
      <script type="text/javascript">
        var disqus_config = function () {
          this.page.url = 'https://arucil.github.io/2018/cps-transformer-implementation/';
          this.page.identifier = '2018/cps-transformer-implementation/';
          this.page.title = 'CPS Transformer的实现';
        };
        var d = document, s = d.createElement('script');
        s.src = 'https://plodsoft.disqus.com/embed.js';
        s.setAttribute('data-timestamp', '' + +new Date());
        (d.head || d.body).appendChild(s);
      </script>
    

  




	





  










  





  

  

  

  
  
    <script type="text/x-mathjax-config">
      MathJax.Hub.Config({
        tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
        }
      });
    </script>

    <script type="text/x-mathjax-config">
      MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
      });
    </script>
    <script type="text/javascript" src="//cdn.bootcss.com/mathjax/2.7.1/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
  


  

  

</body>
</html>
